//给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 
//
// 
// 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。 
// 
//
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。 
//
// 
//
// 示例 1： 
//
// 
//输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
//输出：4
//解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
//其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 
//n 的值 3 。
// 
//
// 示例 2： 
//
// 
//输入：strs = ["10", "0", "1"], m = 1, n = 1
//输出：2
//解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= strs.length <= 600 
// 1 <= strs[i].length <= 100 
// strs[i] 仅由 '0' 和 '1' 组成 
// 1 <= m, n <= 100 
// 
//
// Related Topics 数组 字符串 动态规划 👍 1297 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2025-11-11 21:55:30
 * @description 474.一和零
 */
public class OnesAndZeroes{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 OnesAndZeroes fun=new OnesAndZeroes();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int findMaxForm1(String[] strs, int m, int n) {
		int length = strs.length;
		// 长度i时，j个0和k个1得到最多的字符串数量
		// 0-1背包问题，二维容量，三维dp
		// 初始dp[0][0][0]=0
		int[][][] dp = new int[length + 1][m + 1][n + 1];

		for (int i = 1; i <= length; i++) {
			int[] zerosOnes = getZerosOnes(strs[i - 1]);
			int zeros = zerosOnes[0], ones = zerosOnes[1];
			for (int j = 0; j <= m; j++) {
				for (int k = 0; k <= n; k++) {
					dp[i][j][k] = dp[i - 1][j][k];
					// 只更新有意义的位置
					if (j >= zeros && k >= ones) {
						dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - zeros][k - ones] + 1);
					}
				}
			}
		}
		return dp[length][m][n];
	}

	public int[] getZerosOnes(String str) {
		int[] zerosOnes = new int[2];
		int length = str.length();
		for (int i = 0; i < length; i++) {
			zerosOnes[str.charAt(i) - '0']++;
		}
		return zerosOnes;
	}
	//空间优化
	public int findMaxForm2(String[] strs, int m, int n) {
		int length = strs.length;
		int[][] dp = new int[m + 1][n + 1];

		for (int i = 0; i < length; i++) {
			int zero=0,one=0;
			for (char c : strs[i].toCharArray()) {
				if(c=='0') zero++;
				else  one++;
			}
			// 最多m个0，n个1，这里要倒序防止覆盖
			for (int j = m; j>=zero; j--) {
				for (int k = n; k >=one; k--) {
					dp[j][k]=Math.max(dp[j][k],dp[j-zero][k-one]+1);
				}
			}
		}
		return dp[m][n];
	}


	//比如 n=m=90，前 3 个字符串总共有 5 个 0 和 6 个 1，
	//那么无论我们怎么选，也选不出几十个 0 和 1，所以上面的代码中，其实有大量的循环是多余的。
	//为此，额外用两个变量 sum0 sum1
	//  分别维护前 i 个字符串中的 0 的个数和 1 的个数（但不能超过 m 和 n）。
	//  循环的时候 j 从 sum开始，k 从 sum1开始。
	//注意这个优化会导致只有一部分 f[j][k] 被更新到，
	// 最大值并没有传递给 f[m][n]，可能留在二维数组中间的某个位置上。所以最后要遍历 f，取其中最大值作为答案。
	public int findMaxForm3(String[] strs, int m, int n) {
		int[][] f = new int[m + 1][n + 1];
		int sum0 = 0;
		int sum1 = 0;
		for (String s : strs) {
			int cnt0 = (int) s.chars().filter(ch -> ch == '0').count();
			int cnt1 = s.length() - cnt0;
			sum0 = Math.min(sum0 + cnt0, m);
			sum1 = Math.min(sum1 + cnt1, n);
			for (int j = sum0; j >= cnt0; j--) {
				for (int k = sum1; k >= cnt1; k--) {
					f[j][k] = Math.max(f[j][k], f[j - cnt0][k - cnt1] + 1);
				}
			}
		}
		// 最大值有可能不是f[m][n],所以还要遍历一次
		int ans = 0;
		for (int[] row : f) {
			for (int v : row) {
				ans = Math.max(ans, v);
			}
		}
		return ans;
	}
	//dfs+记忆化搜索

	public int findMaxForm(String[] strs, int m, int n) {
		int k = strs.length;
		// 计算每个位置的0 个数，则1个数为len-cnt0
		int[] cnt0 = new int[k];
		for (int i = 0; i < k; i++) {
			cnt0[i] = (int) strs[i].chars().filter(ch -> ch == '0').count();
		}

		int[][][] memo = new int[strs.length][m + 1][n + 1];
		for (int[][] mat : memo) {
			for (int[] arr : mat) {
				Arrays.fill(arr, -1); // -1 表示没有计算过
			}
		}
		return dfs(k - 1, m, n, strs, cnt0, memo);
	}
	// 表示在0~i选字符串，最多j个0，k个1，最多可以选多少个字符串
	private int dfs(int i, int j, int k, String[] strs, int[] cnt0, int[][][] memo) {
		if (i < 0) {
			return 0;
		}
		if (memo[i][j][k] != -1) { // 之前计算过
			return memo[i][j][k];
		}
		// 不选 strs[i]
		int res = dfs(i - 1, j, k, strs, cnt0, memo);
		int cnt1 = strs[i].length() - cnt0[i];
		// 只更新有意义的位置
		if (j >= cnt0[i] && k >= cnt1) {
			// 选 strs[i]
			res = Math.max(res, dfs(i - 1, j - cnt0[i], k - cnt1, strs, cnt0, memo) + 1);
		}
		return memo[i][j][k] = res; // 记忆化
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
